package Leetcode;

public class problem215 {
    public static int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length < k){
            return 0;
        }
        return qSort(nums,0,nums.length - 1,nums.length - k);
    }

    public static int qSort(int[] nums,int left,int right,int k){
        if(left <= right){
            int[] p = partition(nums,left,right);
            if(k <= p[0]){
                return qSort(nums,left,p[0],k);
            }else if(k >= p[1]){
                return qSort(nums,p[1],right,k);
            }else{
                return nums[k];
            }
        }
        return -1;
    }

    public static int[] partition(int[] nums,int left,int right){
        int index = left - 1;
        int random = (int) (Math.random() * (right - left) + left);
        swap(nums,right,random);
        int flag = nums[right];
        int rindex = right;
        while(left < rindex){
            if(nums[left] < flag){
                swap(nums,++index,left++);
            }else if(nums[left] > flag){
                swap(nums,left,--rindex);
            }else{
                left++;
            }
        }
        swap(nums,rindex,right);

        return new int[]{index,rindex+1};

    }

    public static void swap(int[] arr,int left,int right){
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

}
